#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include "undirected-graph.h"
#define NUM_THREADS 8

int n, m;
UGraph *g;
double **result;
double localMax[1001];

void readGraph() {
  int i, x, y;
  double cost;
  scanf(" %d %d", &n, &m);
  for(i=0; i<m; i++) {
    scanf(" %d %d %lf", &x, &y, &cost);
    addEdge(g, x, y, cost);
  }
}

int main(int argc, char *argv[]) {
  int i, globalMin = INF;
  int num_threads;

  if(argc == 2) {
    num_threads = atoi(argv[1]);
    omp_set_num_threads(num_threads);
  } else {
    num_threads = NUM_THREADS;
    omp_set_num_threads(num_threads);
  }

  result = (double **) malloc(num_threads*sizeof(double *));
  for(i=0; i<num_threads; i++) 
    result[i] = (double *) malloc(1001*sizeof(double));

  g = newUGraph();
  readGraph();

#pragma omp parallel for
  for(i=0; i<g->size; i++) {
    int j;
    int thread_num = omp_get_thread_num();
    dijkstra(g, g->used[i], result[thread_num]);
    localMax[g->used[i]] = 0;
    for(j=0; j<g->size; j++) {
      if( result[thread_num][g->used[j]] > localMax[g->used[i]] )
        localMax[g->used[i]] = result[thread_num][g->used[j]];
    }
  }

  for(i=0; i<g->size; i++) {
    if (localMax[g->used[i]] < globalMin)
      globalMin = localMax[g->used[i]];
  }

  printf("%d\n", globalMin);
  return 0;
}
